package 牛客.二叉树;

import 剑指offer.TreeNode;

public class BM36判断是不是平衡二叉树 {
    public boolean IsBalanced_Solution(TreeNode root) {
        //树形dp套路
        return fun(root).isBanlance;
    }

    public static class returnType {
        public boolean isBanlance;
        public int height;

        public returnType(boolean isBanlance, int height) {
            this.isBanlance = isBanlance;
            this.height = height;
        }
    }

    private returnType fun(TreeNode root) {
        if (root==null) {
            return new returnType(true,0);
        }

        returnType left=fun(root.left);
        returnType right=fun(root.right);

        int height=Math.max(left.height,right.height)+1;
        boolean isBanlance=left.isBanlance && right.isBanlance && Math.abs(right.height-left.height)<2;
        return new returnType(isBanlance,height);
    }


}
